package com.dbh.alg.algorithm.hot100.图论;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode994_腐烂的橘子 {

    public int orangesRotting(int[][] grid) {
        // 先统计所有新鲜橘子数量,并将坏橘子加入对列中
        int freshOrangeCount = 0;
        Queue<int[]> queue = new LinkedList<>();
        int rows = grid.length;
        int cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    freshOrangeCount++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j, 0});
                }
            }
        }
        if(freshOrangeCount == 0) {
            return 0;
        }
        // 定义4个方向
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxTime = 0;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int r = poll[0];
            int c = poll[1];
            int time = poll[2];
            maxTime = Math.max(maxTime, time);
            for (int[] dir : directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    freshOrangeCount--;
                    queue.offer(new int[]{nr, nc, time + 1});
                }
            }
        }
        return freshOrangeCount == 0 ? maxTime : -1;
    }
}
